package com.jiang.专题.动态规划.Q300;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/29 20:02
 */
class Solution {
    // 贪心 + 二分查找
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len + 1];
        arr[1] = nums[0];
        int position = 1;
        for (int i = 1; i < len; i++) {
            if (arr[position] < nums[i]) {
                arr[++position] = nums[i];
            } else {
                // 找到第一个比nums[i]大于或等于的，并替换
                int l = 1, r = position, pos = 0;// 如果找不到说明所有的数都比 nums[i] 大,  就要更新arr[1]
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (arr[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                arr[pos + 1] = nums[i];
            }
        }
        return position;
    }

    // 动态规划
    // public int lengthOfLIS(int[] nums) {
    //     int len = nums.length;
    //     int[] dp = new int[len];
    //     Arrays.fill(dp, 1);
    //     int res = 0;
    //     for (int i = 0; i < len; i++) {
    //         int j = i - 1;
    //         while(j >= 0) {
    //             if (nums[i] > nums[j]) {
    //                 dp[i] = Math.max(dp[i], dp[j] + 1);
    //             }
    //             j--;
    //         }
    //         res = Math.max(dp[i], res);
    //     }
    //     return res;
    // }
}
